import { scan } from './LexParser.js';

// 根据 BNF  参考 abnf 构建语法树

let syntax = {
  // Program 最顶层的输入  Statement 声明  StatementList因为用 + 表示不了
  // Non-terminal Symbol 由其他的 Symbol 组合而成  右边为非终结符 
  Program: [['StatementList', 'EOF']], 
  StatementList: [
    ['Statement'],
    ['StatementList', 'Statement']
  ],
  Statement: [
    ['ExpressionStatement'],
    ['IfStatement'],
    ['VariableDeclaration'],
    ['FunctionDeclaration']
  ],
  IfStatement: [
    ['if', '(', 'Expression', ')', 'Statement']
  ],
  VariableDeclaration: [
    ['var', 'Identifier', ';'],
    ['let', 'Identifier', ';']
  ],
  FunctionDeclaration: [ // 暂时只允许没有参数的 function， 函数体里面 又是一个program
    ['function', 'Identifier', '(', ')', '{', 'StatementList', '}']
  ],
  ExpressionStatement: [
    ['Expression', ';']
  ],
  Expression: [
    ['AdditiveExpression']
  ],
  AdditiveExpression: [ // 加法表示
    ['MultiplicativeExpression'],
    ['AdditiveExpression', '+', 'MultiplicativeExpression'],
    ['AdditiveExpression', '-', 'MultiplicativeExpression']
  ],
  MultiplicativeExpression: [ // 乘法表示
    ['PrimaryExpression'],
    ['MultiplicativeExpression', '*', 'PrimaryExpression'],
    ['MultiplicativeExpression', '/', 'PrimaryExpression']
  ],
  PrimaryExpression: [ // 最主要的
    ['(', 'Expression', ')']
    ['Literal'],
    ['Identifier'] // 标识符
  ],
  Literal: [ // 字面量
    ['NumbericLiteral'], // 七种基本类型 能直接写出来的有四种  Object、Array、Function构造不出来
    ['StringLiteral'],
    ['BooleanLiteral'],
    ['NullLiteral'],
    ['RegularExpression']
  ]
}

let hash = {} // 用来判断state里是否有相同的结构 避免死循环

function closure(state) { // 求 closure
  // 趁state还没被改变时先存起来
  hash[JSON.stringify(state)] = state
  
  let queue = []
  
  // 展开语法树 也是广度优选搜索的过程
  for (let symbol in state) {
    if(symbol.match(/^\$/)) {
      return
    }
    queue.push(symbol) // 把state上面所有的symbol 存进来
  }

  while(queue.length) { // 广度优选搜索的循环
    let symbol = queue.shift() // 每次先取出来一个 入队 Enqueue 出队 Dequeue

    console.log(symbol)

    // 拿这个symbol 去语法树里找这个规则
    if(syntax[symbol]) { // 判断 是否是非终结符 终结符不会出现 syntax tree里面
      for(let rule of syntax[symbol]) {
        // console.log(rule[0]) 入队前先判断是否存在
        if(!state[rule[0]]) queue.push(rule[0])

        let current = state // 要把rule里面每一个symbol的部分都连接起来
        for(let part of rule) {
          // 有些sate之间有相同的地方，需要排除
          if(!current[part]) current[part] = {} // current[part]变成一个新的state
          // 前进一位
          current = current[part]
        }
        // 形成一个新的规则
        current.$reduceType = symbol
        current.$reduceLength = rule.length
      }
    }

  }
  // 这一层的已经和之前循环的结构不一样了
  for(let symbol in state) {
    if(symbol.match(/^\$/)) return
    // console.log(symbol)
    if(hash[JSON.stringify(state[symbol])]) // 判断state是否有
      state[symbol] = hash[JSON.stringify(state[symbol])]
    else closure(state[symbol])
  }

}

// 定义两个状态
let end = {
  $isEnd: true
}

let start = {
  'Program': end
}

closure(start)



function parse(source) { // 把源代码变成一棵语法树
  let stack = [start] // 先进入开始状态 把每一个state存进栈里面
  let symbolStack = [] // 防止children的顺序错误

  function reduce() {
    let state = stack[stack.length - 1]

    if(state.$reduceType) { // 把存进栈里的状态弹出
      let children = []
      for(let i = 0; i < state.$reduceLength; i++) {
        stack.pop()
        children.push(symbolStack.pop())

      }
        // create a nonterminal symbol and shift it
        // shift({
        //   type: state.$reduceType,
        //   children: children.reverse() // 顺序的相反的要反转一下
        // })
        return {
          type: state.$reduceType,
          children: children.reverse() // 顺序的相反的要反转一下
        }
    } else {
      throw new Error('unexpected token')
    }
  }

  function shift(symbol) { // 处理for循环里的内容可以叫shift
    let state = stack[stack.length - 1] // 每次拿到一个新的状态时 栈顶当成当前状态

    if(symbol.type in state) { // 保存一路的状态
      // console.log(state)
      stack.push(state[symbol.type])
      symbolStack.push(symbol)
    } else {
      /*reduce to non-terminal symbols 合成非终结符 */ 
      // reduce()
      shift(reduce())
      shift(symbol) // 因为实际上symbol还是没有办法存进去，还要再shift一次
    }
  }
 
  for(let symbol/*terminal symbols */ of scan(source)) {
    // console.log(symbol)
    shift(symbol)
  }
  // console.log(state)
  // console.log(reduce())
  return reduce()
}

// parse(source)

let evaluator = {
  Program(node) {
    // console.log(node)
    return evaluate(node.children[0])
  },
  StatementList(node) {
    // console.log(node)
    if (node.children.length === 1) {
      return evaluate(node.children[0])
    } else { // js标准里面的定义
      evaluate(node.children[0])
      return evaluate(node.children[1])
    }
  },
  // Statement: [
  //   ['ExpressionStatement'],
  //   ['IfStatement'],
  //   ['VariableDeclaration'],
  //   ['FunctionDeclaration']
  // ],
  Statement(node) {
    return evaluate(node.children[0])
  },
  VariableDeclaration(node) { // 运行时，变量需要执行
    console.log("Declare variable", node.children[1].name)
  },
  EOF() {
    return null
  }

}

function evaluate(node) { // 逐级的执行语法树
  // console.log(node)
  if (evaluator[node.type]) {
    return evaluator[node.type](node)
  }
}

// --------------------------------------------------------------------

let source = `
  var a;
  var c;
`

let tree = parse(source)

evaluate(tree)
